#include <stdio.h>
#include <stdlib.h>
#include "plansza.h"



struct list * zdejmijLista ( struct list *lista )
{
    struct list * cur = lista;

    if(cur==0) return lista;
    if(cur->next==0)
    {
        free(cur);
        lista=0;
    }
    else
    {
            while(cur->next->next!=0)
                cur=cur->next;
            //printf("Usuwa: %d", cur->next->key);
            free(cur->next);
            cur->next=0;
    }
    return lista;
}


 void printlist ( struct list *p )
   {
      struct list *temp;
      temp = p;
      printf("LISTA:");
      if(p!= 0)
      {
            do
            {
                printf(" %d ",temp->key);
                temp=temp->next;
            } while (temp!= 0);
      }
      else
         printf("pusta");
   }


struct list * KopiujListe(struct list *lista)
{
    struct list * nowaLista=0;
    struct list * nowy;
    struct list * last;

    if(lista)
    {

        nowy = ( struct list *)malloc(sizeof(struct list));
        nowy->key = lista->key;
        nowy->next = 0;
        nowaLista = nowy;
        last=nowaLista;
        lista=lista->next;
    }
    while(lista)
    {
        nowy = ( struct list *)malloc(sizeof(struct list));
        nowy->key = lista->key;
        nowy->next = 0;
        last->next = nowy;
        last = nowy;
        lista=lista->next;
    }
    return nowaLista;
}

struct list * UsunListe ( struct list *lista )

 {
     struct list *tmp;

     while(lista)
     {
         tmp = lista;
         lista = lista->next;
         free(tmp);
     }
     return lista;
 }


struct list * dodajRuchSekwencji(struct list *lista, int key, enum pionek gracz)
{
    if(gracz==Bialy)
        return listDodajNaKoniec(lista, key);
    else
        return listDodajNaKoniec(lista, 31-key);

}

int sprawdzRuch(struct list * ruchy, int liczba_ruchow)
{
    int i=0;
    bool dopasowano = false;
    bool rowne;
    struct list *tmpRuchy;
    struct list *tmpWzorzec;
    do
    {
        tmpRuchy = ruchy;
        tmpWzorzec = sekwencja[i];
        rowne = true;
        while (tmpRuchy && tmpWzorzec && rowne) //wychodzimy gdy nie rowne lub jedna z list się kończy
        {
            if(tmpRuchy->key != tmpWzorzec->key) rowne = false;
            tmpRuchy = tmpRuchy->next;
            tmpWzorzec = tmpWzorzec->next;
        }
        if(rowne && (tmpRuchy==0) && (tmpWzorzec==0)) dopasowano = true;
        i++;
    } while((!dopasowano) && (i<liczba_ruchow));

    if(dopasowano) return --i;
    else return -1;
}


void nowa_plansza(struct poleStruct pole[])
{
        int x;
	for(x=0;x<12;x++)
	{
		pole[x].typ=Bialy;
		pole[20+x].typ=Czarny;
	}
	for(x=12;x<20;x++)
		pole[x].typ=Pusty;
};


void plansza(struct poleStruct pole[])
{

    nowa_plansza(pole);
    int x=0;
    for(x=0;x<32;x++)pole[x].lp=x;


    // tworzenie pwowiazan miedzy polami
    for(x=0;x<4;x++)
    {
        pole[x].prawy=&pole[x+4];
        pole[x+8].prawy=&pole[x+4+8];
        pole[x+16].prawy=&pole[x+4+16];
        pole[x+24].prawy=&pole[x+4+24];
        pole[4+x].lewy=&pole[x+8];
        pole[12+x].lewy=&pole[x+16];
        pole[20+x].lewy=&pole[x+24];
        pole[4+x].lewy=&pole[x+4+4];
    }

    for(x=0;x<3;x++)
    {
        pole[4+x].prawy=&pole[4+5+x];
        pole[12+x].prawy=&pole[12+5+x];
        pole[20+x].prawy=&pole[20+5+x];

        pole[1+x].lewy=&pole[4+x];
        pole[9+x].lewy=&pole[12+x];
        pole[17+x].lewy=&pole[20+x];
        pole[25+x].lewy=&pole[28+x];
    }
    pole[0].lewy=0;
    pole[8].lewy=0;
    pole[16].lewy=0;
    pole[24].lewy=0;

    pole[28].lewy=0;
    pole[29].lewy=0;
    pole[30].lewy=0;
    pole[31].lewy=0;

    pole[28].prawy=0;
    pole[29].prawy=0;
    pole[30].prawy=0;
    pole[31].prawy=0;

    pole[7].prawy=0;
    pole[15].prawy=0;
    pole[23].prawy=0;

    for(x=0;x<32;x++)
    {
        pole[x].tlewy=0;
        pole[x].tprawy=0;
    };

    for(x=0;x<32;x++)
    {
        if(pole[x].lewy!=0)
            pole[pole[x].lewy->lp].tprawy=&pole[x];
        if(pole[x].prawy!=0)
            pole[pole[x].prawy->lp].tlewy=&pole[x];
    };

};

// test
void wyswietlPolaczenia(struct poleStruct pole[])
{
    int tmp;
    for(tmp=0; tmp<32; tmp++)
    {
        printf("%d\n",pole[tmp].lp);
        if (pole[tmp].lewy!=0) printf("L: %d\n", pole[tmp].lewy->lp);
        if (pole[tmp].prawy!=0) printf("P: %d\n", pole[tmp].prawy->lp);
        if (pole[tmp].tlewy!=0) printf("TL: %d\n", pole[tmp].tlewy->lp);
        if (pole[tmp].tprawy!=0) printf("TP: %d\n", pole[tmp].tprawy->lp);
        printf("\n");
    }
};

//odwraca plansze
void odwroc(struct poleStruct pole[])
{
	enum pionek temp[32];
        int i;
	for(i=0;i<32;i++)
		temp[i]=pole[31-i].typ;

	for(i=0;i<32;i++)
		pole[i].typ=temp[i];
}


enum pionek czyj_pionek(enum pionek figura)
{
	if((figura==Bialy)||(figura==BialaDamka))return Bialy;
	if((figura==Czarny)||(figura==CzarnaDamka))return Czarny;
	return Pusty;
}

//sprawdza czy jeden z graczy wygrał
bool czyKoniec(struct poleStruct pole[])
{

    int i;
    bool cz=false, b = false;

    for(i=0;i<32;i++)
        if(czyj_pionek(pole[i].typ) == Czarny)
            cz = true;
        else if(czyj_pionek(pole[i].typ) == Bialy)
            b = true;

    return !(cz*b);
}

void ustawPlansze(struct poleStruct pole[], int nrSekw)
{
    int i;
    for(i=0;i<32;i++)
        pole[i].typ = sytuacja_ruchu[nrSekw].pole[i];
}

enum pionek czyja_damka(enum pionek gracz)
{
	if(gracz==Bialy)return BialaDamka;
		else return CzarnaDamka;
}


enum pionek przeciwny(enum pionek gracz)
{
	if(gracz==Bialy)return Czarny;
	if(gracz==BialaDamka)return CzarnaDamka;
	if(gracz==Czarny)return Bialy;
	if(gracz==CzarnaDamka)return BialaDamka;
	return Pusty;
}

//zamiana na damki po dojsciu na pozycje damkowe
void czy_damki(struct poleStruct pole[], bool czy_plansza_odwrocona)

{
        int i=0;
	if(czy_plansza_odwrocona)
	{
		for(i=0;i<4;i++)
		{
			if(pole[i+28].typ==Czarny)
				pole[i+28].typ=CzarnaDamka;
			if(pole[i].typ==Bialy)
				pole[i].typ=BialaDamka;
		}
	} else
	{
		for(i=0;i<4;i++)
		{
			if(pole[i].typ==Czarny)
				pole[i].typ=CzarnaDamka;
			if(pole[i+28].typ==Bialy)
				pole[i+28].typ=BialaDamka;
		}
	}

}


//dodaje plansze z dokonanym przesunieciem, biciami
void dodaj_plansze(struct poleStruct pole[], int *liczba_ruchow, enum pionek gracz)
{


	if(*liczba_ruchow>200)return;
	int j;

	czy_damki(pole,true);

	if(gracz==Bialy)
		for(j=0;j<32;j++)
		{
			if(pole[j].typ==Zbity)
                            sytuacja_ruchu[*liczba_ruchow].pole[j]=Pusty;
			else
                            sytuacja_ruchu[*liczba_ruchow].pole[j]=pole[j].typ;

		}
	  else
		for(j=0;j<32;j++)
		{
			if(pole[31-j].typ==Zbity)
                            sytuacja_ruchu[*liczba_ruchow].pole[j]=Pusty;
			else
                            sytuacja_ruchu[*liczba_ruchow].pole[j]=pole[31-j].typ;
		};

	*liczba_ruchow=*liczba_ruchow+1;
	return;
}


//sprawdza mozliwe ruchy
bool bicia_rekurencja(struct poleStruct pole[], int *ile_zbitych, int *max_zbitych, int *liczba_ruchow, enum pionek gracz,int nr1, int nr2, int nr3, struct list *tmpSeq)
{

    //jeśli bicie - na sąsiednim polu przeciwnik i puste za przeciwnikiem
    if ( ( czyj_pionek(pole[nr2].typ)==czyj_pionek(przeciwny(gracz)) ) &&(pole[nr3].typ==Pusty) )
            {
                *ile_zbitych=*ile_zbitych+1;
                pole[nr3].typ=gracz; //
                pole[nr1].typ=Pusty;
                printf("BICIE: %d do %d\n", nr1, nr3);
                enum pionek tmp=pole[nr2].typ;
                pole[nr2].typ=Zbity;
                tmpSeq = dodajRuchSekwencji(tmpSeq, nr3, gracz); //tworzymy liste ruchow

                if(!sprawdz_bicie(pole, gracz, nr3, ile_zbitych, max_zbitych, liczba_ruchow, tmpSeq))
                {
                        if(*ile_zbitych>=*max_zbitych)
                                    {
                                            //printf("ustawiamy tylko ten ruch %d\n", *max_zbitych);
                                            if(*ile_zbitych>*max_zbitych)
                                                    {
                                                            *max_zbitych=*ile_zbitych;
                                                            *liczba_ruchow=0;
                                                            printf("Zeruje ruchy%d\n", *ile_zbitych);
                                                    }

                                            sekwencja[*liczba_ruchow] = KopiujListe(tmpSeq);
                                            dodaj_plansze(pole, liczba_ruchow, gracz);

                                    }

                }
                tmpSeq = zdejmijLista(tmpSeq); //cofamy się wstecz - zdejmujemy ostatni ruch z listy
                pole[nr2].typ=tmp;
                pole[nr3].typ=Pusty;
                pole[nr1].typ=gracz;

                *ile_zbitych=*ile_zbitych-1;
                return true;

            } else return false;
};



struct poleStruct * wskaz(char kierunek, struct poleStruct* ptr)
{
	switch(kierunek)
	{
		case 1 : return ptr->tprawy;
		case 2 : return ptr->tlewy;
		case 3 : return ptr->lewy;
		case 4 : return ptr->prawy;
	};
	return ptr;
}


//sprawdza bicie damki
bool bicia_damki_rekurencja(struct poleStruct pole[], int *ile_zbitych, int *max_zbitych, int *liczba_ruchow, enum pionek gracz, char kierunek, int nr, struct list *tmpSeq)
{
	struct poleStruct* ptr, *ptr_prev;
	enum pionek tmp;

	ptr=wskaz(kierunek, &pole[nr]);
	while((ptr!=NULL)&&(ptr->typ==Pusty))	//idzie w lewy tyl az napotka jakis pionek lub koniec planszy
		ptr=wskaz(kierunek, ptr);
	if(ptr==NULL)return false;  //jesli koniec planszy
	if(ptr->typ==Zbity)return false; //spr
	if((czyj_pionek(ptr->typ)==przeciwny(gracz)))	//i napotkalismy pionek przeciwnika
			{
				*ile_zbitych=*ile_zbitych+1;

				tmp=ptr->typ;
				ptr->typ=Zbity;  //kasujemy bitego chwilowo
				ptr_prev=ptr;
				//to jesli pozycje za nim sa wolne dodsajemy wszystkie do mozliwych ruchow
				ptr=wskaz(kierunek, ptr);
                                if(ptr)
                                {
                                    printf("PTR D");
                                    tmpSeq = dodajRuchSekwencji(tmpSeq, ptr->lp, gracz);
                                }
				while((ptr!=NULL)&&(ptr->typ==Pusty))
				{
                                        printf("Bity D: %d \n", ptr->lp);
					pole[ptr->lp].typ=czyja_damka(gracz);
					if(*ile_zbitych>=*max_zbitych)
					{
						if(*ile_zbitych>*max_zbitych)
						{
							*max_zbitych=*ile_zbitych;
							*liczba_ruchow=0;
                                                        printf("Zeruje D: %d \n", *max_zbitych);
						}
                                                sekwencja[*liczba_ruchow] = KopiujListe(tmpSeq);
						dodaj_plansze(pole, liczba_ruchow, gracz);
					}
					sprawdz_bicie_damki(pole, ile_zbitych, max_zbitych, liczba_ruchow, gracz, ptr->lp, tmpSeq);
					pole[ptr->lp].typ=Pusty;
					ptr=wskaz(kierunek, ptr);
				}
                                  if(ptr)
                                {
                                    tmpSeq = zdejmijLista(tmpSeq);
                                }
				ptr=ptr_prev;  // powroty z rekursji
				ptr->typ=tmp;  //odtwarzamy zbitego pionka

				*ile_zbitych=*ile_zbitych-1;
			}
	return false;
}

//czy są bicia
bool sprawdz_bicie(struct poleStruct pole[], enum pionek gracz, int nr, int *ile_zbitych, int *max_zbitych, int *liczba_ruchow, struct list *tmpSeq)
{
	bool czy_znalazl=false;

	//btw. nie potrzebnie sprawdze np. .lewy->lewy bo jesli na nr nie stoi nic to nie ma mowy o biciu
	if((pole[nr].lewy!=NULL)&&(pole[nr].lewy->lewy!=NULL))
		czy_znalazl=bicia_rekurencja(pole, ile_zbitych, max_zbitych, liczba_ruchow, gracz, nr, pole[nr].lewy->lp, pole[nr].lewy->lewy->lp, tmpSeq);

	if((pole[nr].prawy!=NULL)&&(pole[nr].prawy->prawy!=NULL))
		czy_znalazl=bicia_rekurencja(pole, ile_zbitych, max_zbitych, liczba_ruchow, gracz, nr, pole[nr].prawy->lp, pole[nr].prawy->prawy->lp, tmpSeq)||czy_znalazl;

	if((pole[nr].tlewy!=NULL)&&(pole[nr].tlewy->tlewy!=NULL))
		czy_znalazl=bicia_rekurencja(pole, ile_zbitych, max_zbitych, liczba_ruchow, gracz, nr, pole[nr].tlewy->lp, pole[nr].tlewy->tlewy->lp, tmpSeq)||czy_znalazl;
	if((pole[nr].tprawy!=NULL)&&(pole[nr].tprawy->tprawy!=NULL))
		czy_znalazl=bicia_rekurencja(pole, ile_zbitych, max_zbitych, liczba_ruchow, gracz, nr, pole[nr].tprawy->lp, pole[nr].tprawy->tprawy->lp, tmpSeq)||czy_znalazl;
	return czy_znalazl;
}


// czy są bicia damki
bool sprawdz_bicie_damki(struct poleStruct pole[], int *ile_zbitych, int *max_zbitych, int *liczba_ruchow, enum pionek gracz, int nr, struct list *tmpSeq)
{

	pole[nr].typ=Pusty;
	//tyl-lewo
	bicia_damki_rekurencja(pole, ile_zbitych, max_zbitych, liczba_ruchow, gracz, 1, nr, tmpSeq);
	bicia_damki_rekurencja(pole, ile_zbitych, max_zbitych, liczba_ruchow, gracz, 2, nr, tmpSeq);
	bicia_damki_rekurencja(pole, ile_zbitych, max_zbitych, liczba_ruchow, gracz, 3, nr, tmpSeq);
	bicia_damki_rekurencja(pole, ile_zbitych, max_zbitych, liczba_ruchow, gracz, 4, nr, tmpSeq);

	pole[nr].typ=czyja_damka(gracz);
	return false;
}


//znajdź wszystkie możliwe ruchy
void szukaj_ruchy(struct poleStruct pole[], int *liczba_ruchow, enum pionek gracz)
{

    int i;

    if(gracz==Czarny)odwroc(pole);

    //sprawdzamy po kolei ruchy naszych pionkow i dopisujemy do valid_moves;
    //*liczba_ruchow=0;

    //jesli damki wogole sa na planszy ??? dsopisac
    //bicia damek
    enum pionek damka=czyja_damka(gracz);

    int ile_zbitych=0;
    int max_zbitych=0;
    struct list *tmpSeq=0;
    //najpierw bicia, wówczas zwykłe ruchy są niepotrzebne
    for(i=0;i<32;i++)
    {

            //bicia zwyklych pionkow
            if(pole[i].typ==gracz)
            {
                tmpSeq = dodajRuchSekwencji(tmpSeq, i, gracz); //dodajemy do listy ruchow pole startowe
                sprawdz_bicie(pole, gracz, i, &ile_zbitych, &max_zbitych, liczba_ruchow, tmpSeq);
                tmpSeq = zdejmijLista(tmpSeq);
            }
            else
            //bicia damek
            if(pole[i].typ==damka)
            {
                tmpSeq = dodajRuchSekwencji(tmpSeq, i, gracz);
                sprawdz_bicie_damki(pole, &ile_zbitych, &max_zbitych, liczba_ruchow, gracz, i, tmpSeq);
                tmpSeq = zdejmijLista(tmpSeq);
            }
            ile_zbitych=0;
    }

    //gdy brak bić szukamy zwykłych ruchów
   if(!*liczba_ruchow)
   {
	//ruchy damek - bez bić
	enum pionek tmp;

	if(gracz==Bialy)
            tmp=BialaDamka;
	else
            tmp=CzarnaDamka;


	for(i=0;i<32;i++)   //szuka ruchu damki
            if(pole[i].typ==tmp)
            {
                    pole[i].typ=Pusty;
                    struct poleStruct* ptr;
                    //tyl-lewo
                    ptr=pole[i].tlewy;
                    while((ptr!=NULL)&&(ptr->typ==Pusty))
                    {
                            pole[ptr->lp].typ=tmp;

                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], pole[i].lp, gracz); //poczatkowa pozycja
                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], ptr->lp, gracz); //koncowa pozycja
                            dodaj_plansze(pole, liczba_ruchow, gracz);
                            pole[ptr->lp].typ=Pusty;
                            ptr=ptr->tlewy; //szukamy nast. wolnych - damka może przejść przez kilka pól
                    };
                    //tyl-prawo
                    ptr=pole[i].tprawy;
                    while((ptr!=NULL)&&(ptr->typ==Pusty))
                    {
                            pole[ptr->lp].typ=tmp;
                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], pole[i].lp, gracz); //poczatkowa pozycja
                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], ptr->lp, gracz); //koncowa pozycja
                            dodaj_plansze(pole, liczba_ruchow, gracz);
                            pole[ptr->lp].typ=Pusty;
                            ptr=ptr->tprawy;
                    };
                    //przod-lewo
                    ptr=pole[i].lewy;
                    while((ptr!=NULL)&&(ptr->typ==Pusty))
                    {
                            pole[ptr->lp].typ=tmp;
                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], pole[i].lp, gracz); //poczatkowa pozycja
                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], ptr->lp, gracz); //koncowa pozycja
                            dodaj_plansze(pole, liczba_ruchow, gracz);
                            pole[ptr->lp].typ=Pusty;
                            ptr=ptr->lewy;
                    };
                    //przod-prawo
                    ptr=pole[i].prawy;
                    while((ptr!=NULL)&&(ptr->typ==Pusty))
                    {
                            pole[ptr->lp].typ=tmp;
                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], pole[i].lp, gracz); //poczatkowa pozycja
                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], ptr->lp, gracz); //koncowa pozycja
                            dodaj_plansze(pole, liczba_ruchow, gracz);
                            pole[ptr->lp].typ=Pusty;
                            ptr=ptr->prawy;
                    };

                    pole[i].typ=tmp;
            }


	//normalne ruchy - bez bić

	for(i=0;i<28;i++) // bierzemy pod uwage pionki, ktore nie sa na pozycjach damkowych
	{

            if(pole[i].typ==gracz)
            {
                    if((pole[i].lewy!=NULL)&&(pole[i].lewy->typ==Pusty))
                    {
                            enum pionek tmp=pole[i].typ;
                            pole[i].lewy->typ=tmp;
                            pole[i].typ=Pusty;
                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], pole[i].lp, gracz); //poczatkowa pozycja
                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], pole[i].lewy->lp, gracz); //koncowa pozycja
                            dodaj_plansze(pole, liczba_ruchow, gracz);
                            pole[i].lewy->typ=Pusty;
                            pole[i].typ=tmp;
                    }

                    if((pole[i].prawy!=NULL)&&(pole[i].prawy->typ==Pusty))
                    {
                            enum pionek tmp=pole[i].typ;
                            pole[i].prawy->typ=tmp;
                            pole[i].typ=Pusty;
                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], pole[i].lp, gracz);
                            sekwencja[*liczba_ruchow] = dodajRuchSekwencji(sekwencja[*liczba_ruchow], pole[i].prawy->lp, gracz);
                            dodaj_plansze(pole, liczba_ruchow, gracz);
                            pole[i].prawy->typ=Pusty;
                            pole[i].typ=tmp;

                    }


            }
	}

   }
   if(gracz==Czarny)odwroc(pole);
}


